/*
* Authors: Savenko Maria
*           * * *
*           * * *
* This file contains implementation of polynomial algorithm.
*/



#include "stdafx.h"
#include "polynomial_algorithm.h"



polynomial_algorithm::polynomial_algorithm(graph_t & g_) {
    g = g_;
}


void polynomial_algorithm::assign_weights() {

    graph_traits<graph_t>::vertex_iterator i, iend;

	for(tie(i, iend) = vertices(g); i != iend; ++i) {
        g[*i].weight = 0.5;
	}
}


void polynomial_algorithm::run(){
    cout << "Algorithm using polynomials started..." << endl;

    assign_weights();

    graph_traits<graph_t>::vertex_iterator i, iend;
    
    //calculating for each vertex if it's weight should be 1 or 0
	for(tie(i, iend) = vertices(g); i != iend; ++i) {
        if (out_degree(*i,g) == 0 || A_polynomial(*i, NULL) > B_polynomial(*i))
            g[*i].weight = 0;
        else g[*i].weight = 1;
	}

    //if where is a group of verteces with weight 1 - one of them should take the 0 weight
    for(tie(i, iend) = vertices(g); i != iend; ++i) {
        if (A_polynomial(*i, NULL) == 1)
            g[*i].weight = 0;
	}

    form_independent_set();
}

//"A" polynomial which is in fact a product of neighbours' values fo vertex V 
double polynomial_algorithm::A_polynomial(vertex_t const v, vertex_t omit_v = NULL){
    
    graph_traits<graph_t>::adjacency_iterator i, iend;

    double result = 1;
    for(tie(i, iend) = adjacent_vertices(v, g); i != iend; ++i) {
        if (omit_v != NULL && *i == omit_v)
            continue;
        double const i_weight = g[*i].weight;
        if (i_weight == 0)
            return 0;
        
        result *= i_weight;
	}

    return result;
}

//"B" polynomial which is a summand of products of (1 - V's neighbours' value) on their neighbours' values excluding V
double polynomial_algorithm::B_polynomial(vertex_t const v){
    
    graph_traits<graph_t>::adjacency_iterator i, iend;
    graph_traits<graph_t>::adjacency_iterator vi, viend;
    double result = 0;

    for(tie(i, iend) = adjacent_vertices(v, g); i != iend; ++i) {
        double const i_weight = g[*i].weight;
        if (i_weight != 1){
            result += (1 - i_weight) * A_polynomial(*i, v);
        } 
	}

    return result;
}


void polynomial_algorithm::form_independent_set(){

    graph_traits<graph_t>::vertex_iterator i, iend;

	for(tie(i, iend) = vertices(g); i != iend; ++i) {
        vertex_p const v = g[*i];
        if (v.weight == 0)
            independent_set.push_back(v.name);
	}
}


void polynomial_algorithm::print_independent_set() const{
    
    cout << "Maximum Independent Set found: " << endl;

	for (vertex_list::const_iterator j = independent_set.begin(); j != independent_set.end(); ++j) {
		cout << *j << " ";
	}
	cin.get();
}